package dp;


import java.util.*;

class Solution {

    // 1. 创建 dp 表
    // 2. 初始化
    // 3. 填表
    // 4. 返回值

    /**
     * 1137. 第 N 个泰波那契数
     * @param n
     * @return
     */
    public int tribonacci(int n) {
        if(n == 0) return 0;
        if(n == 1 || n == 2) return 1;
        // 1. 创建 dp 表
        // dp[i]表示：第i个泰波那锲数
        int[] dp = new int[n + 1];
        // 2. 初始化
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        // 3. 填表
        for(int i = 3; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }
        // 4. 返回值
        return dp[n];
    }


    /**
     * 面试题 08.01. 三步问题
     */
    public int waysToStep(int n) {
        if(n == 1 || n == 2) return n;
        if(n == 3) return 4;
        // 1. 创建 dp 表
        // dp[i]表示：到达i位置时，一共有多少种方法
        int MOD = (int)1e9 + 7;
        int[] dp = new int[n + 1];
        // 2. 初始化
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        // 3. 填表
        for(int i = 4; i <= n; i++) {
            dp[i] = ((dp[i-1] + dp[i-2]) % MOD + dp[i-3]) % MOD;
        }

        // 4. 返回值
        return dp[n];
    }

    /**
     * 746. 使用最小花费爬楼梯
     */
    public int minCostClimbingStairs(int[] cost) {
        // 1. 创建 dp 表
        // dp[i]表示：到达i位置时，最小的花费
        int n = cost.length;
        int[] dp = new int[n+1];
        // 2. 初始化
        // 3. 填表
        for(int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
        }
        // 4. 返回值
        return dp[n];
    }



    /**
     *  解码方法
     */
    public int numDecodings(String ss) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int n = ss.length();
        char[] s = ss.toCharArray();
        int[] dp = new int[n];

        // 初始化
        if(s[0] != '0') dp[0] = 1;
        if(n == 1) return dp[0];
        if(s[1] != '0' && s[0] != '0') dp[1] += 1;
        int t = (s[0] - '0') * 10 + s[1] - '0';
        if( t >=  10 && t <= 26) dp[1] += 1;

        for(int i = 2; i < n; i++) {
            if(s[i] != '0') dp[i] += dp[i-1];

            int tt = (s[i-1] - '0') * 10 + s[i] - '0';
            if( tt >=  10 && tt <= 26) dp[i] += dp[i-2];
        }
        return dp[n-1];

    }
    public int numDecodings2(String ss) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int n = ss.length();
        char[] s = ss.toCharArray();
        int[] dp = new int[n + 1];

        // 初始化
        dp[0] = 1; //保证后续填表是正确的

        if(s[1 - 1] != '0') dp[1] = 1;

        for(int i = 2; i <= n; i++) {
            if(s[i - 1] != '0') dp[i] += dp[i-1];

            int tt = (s[i-2] - '0') * 10 + s[i  -1] - '0';
            if( tt >=  10 && tt <= 26) dp[i] += dp[i-2];
        }
        return dp[n];

    }


    /**
     * 不同路径
     */
    public int uniquePaths(int m, int n) {
        // 1. 创建 dp 表
        int[][] dp = new int[m+1][n+1];
        // 2. 初始化
        dp[0][1] = 1;
        // 3. 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        // 4. 返回值
        return dp[m][n];
    }


    /**
     * 不同路径 II
     * @param obstacleGrid
     * @return
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        // 1. 建 dp 表
        int[][] dp = new int[m+1][n+1];
        // 2. 初始化
        dp[0][1] = 1;
        // 3. 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(obstacleGrid[i-1][j-1] == 1) {
                    dp[i][j] = 0;
                }else {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        // 4. 返回值
        return dp[m][n];

    }

    /**
     * LCR 166. 珠宝的最高价值
     * @param frame
     * @return
     */
    public int jewelleryValue(int[][] frame) {
        int m = frame.length;
        int n = frame[0].length;
        // 1. 创建 dp 表
        int[][] dp = new int[m+1][n+1];
        // 2. 初始化
        // 3. 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + frame[i-1][j-1];
            }
        }
        // 4. 返回值
        return dp[m][n];
    }

    /**
     * 下降路径最小和
     */
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        // 1. 创建 dp 表
        int[][] dp = new int[n+1][n+2];
        // 2. 初始化
        for(int i = 1; i <= n; i++) {
            dp[i][0] = Integer.MAX_VALUE;
            dp[i][n+1] = Integer.MAX_VALUE;
        }
        // 3. 填表
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = Math.min(Math.min(dp[i-1][j-1], dp[i-1][j]),dp[i-1][j+1]) + matrix[i-1][j-1];
            }
        }
        // 4. 返回值
        int min = Integer.MAX_VALUE;
        for(int i = 1; i <= n; i++) {
            min = Math.min(min, dp[n][i]);
        }
        return min;
    }

    /**
     * 最小路径和
     */
    public int minPathSum(int[][] grid) {

        // 1. 创建 dp 表
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m+1][n+1];
        // 2. 初始化
        for(int i = 2; i <= n; i++) {
            dp[0][i] = Integer.MAX_VALUE;
        }
        for(int i = 2; i <= m; i++) {
            dp[i][0] = Integer.MAX_VALUE;
        }
        // 3. 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1];
            }
        }
        // 4. 返回值
        return dp[m][n];
    }

    /**
     * 地下城游戏
     */
    public int calculateMinimumHP(int[][] dungeon) {
        // 1. 创建 dp 表
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] dp = new int[m+1][n+1];
        // 2. 初始化
        for(int j = 0; j <= n; j++) {
            dp[m][j] = Integer.MAX_VALUE;
        }
        for(int i = 0; i <= m; i++) {
            dp[i][n] = Integer.MAX_VALUE;
        }
        dp[m][n-1] = dp[m-1][n] = 1;
        // 3. 填表
        for(int i = m-1; i >= 0; i--) {
            for(int j = n-1; j >= 0; j--) {
                dp[i][j] = Math.min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j];
                dp[i][j] = Math.max(1,dp[i][j]);
            }
        }
        // 4. 返回值
        return dp[0][0];
    }


    /**
     * 面试题 17.16. 按摩师
     */
    public int massage(int[] nums) {
        // 1. 创建 dp 表
        int n = nums.length;
        if(n == 0) return 0;
        int[] f = new int[n];
        int[] g = new int[n];
        // 2. 初始化
        f[0] = nums[0];
        // 3. 填表
        for(int i = 1; i < n; i++) {
            f[i] = g[i-1] + nums[i];
            g[i] = Math.max(f[i-1], g[i-1]);
        }
        // 4. 返回值
        return Math.max(g[n-1], f[n-1]);
    }

    /**
     * 打家劫舍 II
     */
    public int rob(int[] nums) {
        int n = nums.length;
        return Math.max(nums[0] + rob1(nums, 2, n-2), rob1(nums, 1, n-1));
    }
    public int rob1(int[] nums, int left, int right) {
        if(left > right) return 0;
        // 1. 创建 dp 表
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        // 2. 初始化
        f[left] = nums[left];
        // 3. 填表
        for(int i = left + 1; i <= right; i++) {
            f[i] = g[i-1] + nums[i];
            g[i] = Math.max(g[i-1], f[i-1]);
        }
        // 4. 返回值
        return  Math.max(f[right], g[right]);
    }


    /**
     * 740. 删除并获得点数
     */
    public int deleteAndEarn(int[] nums) {
        // 预处理
        int n = 10001;
        int[] arr = new int[n];
        for(int x : nums) arr[x] += x;
        // 1. 创建 dp 表
        int[] f = new int[n];
        int[] g = new int[n];
        // 2. 初始化
        f[0] = arr[0];
        // 3. 填表
        for(int i = 1; i < n; i++) {
            f[i] = arr[i] + g[i-1];
            g[i] = Math.max(f[i-1], g[i-1]);
        }
        // 4. 返回值
        return Math.max(f[n-1], g[n-1]);
    }


    /**
     * LCR 091. 粉刷房子
     */
    public int minCost(int[][] costs) {
        // 1. 创建 dp 表
        int m = costs.length;
        int[][] dp = new int[m+1][3];
        // 2. 初始化
        // 3. 填表
        for(int i = 1; i <= m; i++) {
            dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + costs[i-1][0];
            dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + costs[i-1][1];
            dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + costs[i-1][2];
        }
        // 4. 返回值
        return Math.min(Math.min(dp[m][0], dp[m][1]), dp[m][2]);
    }

    /**
     * 309. 买卖股票的最佳时机含冷冻期
     */
    public int maxProfit(int[] prices) {
        // 1. 创建 dp 表
        int n = prices.length;
        int[][] dp = new int[n][3];
        // 2. 初始化
        dp[0][0] = -prices[0];
        // 3. 填表
        for(int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][2]);
            dp[i][2] = dp[i-1][0] + prices[i];
        }
        // 4. 返回值
        return Math.max(dp[n-1][1], dp[n-1][2]);
    }


    /**
     * 714. 买卖股票的最佳时机含手续费
     */
    public int maxProfit(int[] prices, int fee) {
        // 1. 创建 dp 表
        int n = prices.length;
        int[][] dp = new int[n][2];
        // 2. 初始化
        dp[0][0] = -prices[0];
        // 3. 填表
        for(int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i] - fee);
        }
        // 4. 返回值
        return dp[n-1][1];
    }


    /**
     * 123. 买卖股票的最佳时机 III
     */
    public int maxProfit2(int[] prices) {
        // 1. 创建 dp 表
        int n = prices.length;
        int k = 2;
        int[][] f = new int[n][k+1];
        int[][] g = new int[n][k+1];
        // 2. 初始化
        f[0][0] = -prices[0];
        for(int i = 1; i <= k; i++) {
            f[0][i] = -0x3f3f3f3f;
            g[0][i] = -0x3f3f3f3f;
        }
        // 3. 填表
        for(int i = 1; i < n; i++) {
            for(int j = 0; j <= k; j++) {
                f[i][j] = Math.max(f[i-1][j], g[i-1][j] - prices[i]);
                g[i][j] = g[i-1][j];
                if(j - 1 >= 0) {
                    g[i][j] = Math.max(g[i][j], f[i-1][j-1] + prices[i]);
                }
            }
        }
        // 4. 返回值
        int ret = 0;
        for(int i = 0; i <= k; i++) {
            if(g[n-1][i] > ret) {
                ret = g[n-1][i];
            }
        }
        return ret;
    }

    /**
     * 188. 买卖股票的最佳时机 IV
     */
    public int maxProfit(int k, int[] prices) {
        // 1. 创建 dp 表
        int n = prices.length;
        // 优化
        k = Math.min(k, n / 2);
        int[][] f = new int[n][k+1];
        int[][] g = new int[n][k+1];
        // 2. 初始化
        f[0][0] = -prices[0];
        for(int i = 1; i <= k; i++) {
            f[0][i] = -0x3f3f3f3f;
            g[0][i] = -0x3f3f3f3f;
        }
        // 3. 填表
        for(int i = 1; i < n; i++) {
            for(int j = 0; j <= k; j++){
                f[i][j] = Math.max(f[i-1][j], g[i-1][j] - prices[i]);
                g[i][j] = g[i-1][j];
                if(j - 1 >= 0) {
                    g[i][j] = Math.max(g[i][j], f[i-1][j-1] + prices[i]);
                }
            }
        }
        // 4. 返回值
        int ret = 0;
        for(int i = 0; i <= k; i++) {
            if(g[n-1][i] > ret) ret = g[n-1][i];
        }
        return ret;
    }

    /**
     * 53. 最大子数组和
     */
    public int maxSubArray(int[] nums) {
        // 1. 创建 dp 表
        int n = nums.length;
        int[] dp = new int[n+1];
        // 2. 初始化
        // 3. 填表
        int ret = Integer.MIN_VALUE;
        for(int i = 1; i <= n; i++) {
            dp[i] = Math.max(nums[i-1], dp[i-1] + nums[i-1]);
            ret = Math.max(ret, dp[i]);
        }
        // 4. 返回值
        return ret;

    }

    /**
     * 918. 环形子数组的最大和
     */
    public int maxSubarraySumCircular(int[] nums) {
        // 1. 创建 dp 表
        int n = nums.length;
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];
        // 2. 初始化
        // 3. 填表
        int sum = 0;
        int fmax = Integer.MIN_VALUE;
        int gmin = Integer.MAX_VALUE;
        for(int i = 1; i <= n; i++) {
            sum += nums[i-1];
            f[i] = Math.max(nums[i-1], f[i-1] + nums[i-1]);
            fmax = Math.max(fmax, f[i]);
            g[i] = Math.min(nums[i-1], g[i-1] + nums[i-1]);
            gmin = Math.min(gmin, g[i]);
        }
        // 4. 返回值
        return sum == gmin ? fmax : Math.max(fmax, sum - gmin);
    }

    /**
     * 152. 乘积最大子数组
     */
    public int maxProduct(int[] nums) {
        // 1. 创建 dp 表
        int n = nums.length;
        int[] f = new int[n+1];
        int[] g = new int[n+1];
        // 2. 初始化
        f[0] = 1;
        g[0] = 1;
        // 3. 填表
        int ret = Integer.MIN_VALUE;
        for(int i = 1; i <= n; i++) {
            f[i] = Math.max(Math.max(nums[i-1], f[i-1] * nums[i-1]),g[i-1] * nums[i-1]);
            g[i] = Math.min(Math.min(nums[i-1], f[i-1] * nums[i-1]),g[i-1] * nums[i-1]);
            ret = Math.max(ret, f[i]);

        }
        // 4. 返回值
        return ret;


    }


    /**
     * 1567. 乘积为正数的最长子数组长度
     */
    public int getMaxLen(int[] nums) {
        // 1. 创建 dp 表
        int n = nums.length;
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];
        // 2. 初始化
        f[0] = g[0] = 0;
        // 3. 填表
        int ret = 0;
        for(int i = 1; i <= n; i++) {
            if(nums[i - 1] > 0) {
                f[i] = f[i - 1] + 1;
                g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
            } else if(nums[i - 1] < 0) {
                f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
                g[i] = f[i - 1] + 1;
            }
            ret = Math.max(ret, f[i]);
        }
        // 4. 返回值
        return ret;

    }


    /**
     * 413. 等差数列划分
     */
    public int numberOfArithmeticSlices(int[] nums) {
        // 1. 创建 dp 表
        int n = nums.length;
        int[] dp = new int[n];
        // 2. 初始化
        // 3. 填表
        int ret = 0;
        for(int i = 2; i < n; i++) {
            dp[i] = (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) ? dp[i-1] + 1 : 0;
            ret += dp[i];
        }
        // 4. 返回值
        return ret;

    }

    /**
     * 978. 最长湍流子数组
     */
    public int maxTurbulenceSize(int[] arr) {
        // 1. 创建 dp 表
        int n = arr.length;
        int[] f = new int[n];
        int[] g = new int[n];
        // 2. 初始化
        for(int i = 0; i < n; i++) {
            f[i] = g[i] = 1;
        }
        // 3. 填表
        int ret = 1;
        for(int i = 1; i < n; i++) {
            if(arr[i] < arr[i-1]) {
                f[i] = g[i-1] + 1;
            }else if(arr[i] > arr[i-1]) {
                g[i] = f[i-1] + 1;
            }
            ret = Math.max(ret, Math.max(f[i],g[i]));
        }
        // 4. 返回值
        return ret;

    }


    /**
     * 139. 单词拆分
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        // 优化
        Set<String> hash = new HashSet<>(wordDict);
        // 1. 创建 dp 表
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        // 2. 初始化
        dp[0] = true;
        s = " " + s;
        // 3. 填表
        for(int i = 1; i <= n; i++) {
            for(int j = i; j >= 1; j--) {
                if(dp[j-1] && hash.contains(s.substring(j, i+1))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        // 4. 返回值
        return dp[n];
    }

    /**
     * 467. 环绕字符串中唯一的子字符串
     */
    public int findSubstringInWraproundString(String ss) {
        // 1. 创建 dp 表
        int n = ss.length();
        char[] s = ss.toCharArray();
        int[] dp = new int[n];
        // 2. 初始化
        for(int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        // 3. 填表
        for(int i = 1; i < n; i++) {
            if(s[i-1] + 1 == s[i] || (s[i-1] == 'z' && s[i] == 'a')) {
                dp[i] += dp[i-1];
            }
        }
        // 4. 返回值
        // 去重
        int[] hash = new int[26];
        for(int i = 0; i < n; i++) {
            hash[s[i] - 'a'] = Math.max(hash[s[i] - 'a'], dp[i]);
        }
        int sum = 0;
        for(int x : hash) sum += x;
        return sum;
    }

    /**
     * 300. 最长递增子序列
     */
    public int lengthOfLIS(int[] nums) {
        // 1. 创建 dp 表
        int n = nums.length;
        int[] dp = new int[n];
        // 2. 初始化
        for(int i = 0; i < n; i++) dp[i] = 1;
        // 3. 填表
        int ret = 1;
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < i; j++) {
                if(nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ret = Math.max(ret, dp[i]);
        }
        // 4. 返回值
        return ret;

    }

    /**
     * 376. 摆动序列
     */
    public int wiggleMaxLength(int[] nums) {
        // 1. 创建 dp 表
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        // 2. 初始化
        for(int i = 0; i < n; i++) f[i] = g[i] = 1;
        // 3. 填表
        int ret = 1;
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < i; j++) {
                if(nums[i] > nums[j]) {
                    f[i] = Math.max(g[j] + 1, f[i]);
                } else if(nums[i] < nums[j]) {
                    g[i] = Math.max(f[j] + 1, g[i]);
                }
            }
            ret = Math.max(ret, Math.max(f[i], g[i]));
        }
        // 4. 返回值
        return ret;
    }

    /**
     * 673. 最长递增子序列的个数
     */
    public int findNumberOfLIS(int[] nums) {
        // 1. 创建 dp 表
        // len[i]表示：以i位置为结尾的所有子序列中，最长递增子序列的“长度”
        // count[i]表示：以i位置为结尾的所有子序列中，最长递增子序列的“个数”
        int n = nums.length;
        int[] len = new int[n];
        int[] count = new int[n];
        // 2. 初始化
        for(int i = 0; i < n; i++) len[i] = count[i] = 1;
        // 3. 填表
        int retlen = 1;
        int retcount = 1;
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < i; j++) {
                if(nums[j] < nums[i]) {
                    if(len[j] + 1 == len[i]) {
                        count[i] += count[j];
                    } else if(len[j] + 1 > len[i]) {
                        len[i] = len[j] + 1;
                        count[i] = count[j];
                    }
                }
            }
            if(retlen == len[i]) {
                retcount += count[i];
            }else if(retlen < len[i]) {
                retlen = len[i];
                retcount = count[i];
            }
        }
        // 4. 返回值
        return retcount;
    }

    /**
     * 646. 最长数对链
     */
    public int findLongestChain(int[][] pairs) {
        // 预处理
        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
        // 1.创建 dp 表
        // dp[i]表示：以i为结尾的所有数对链中，最长的数对链
        int n = pairs.length;
        int[] dp = new int[n];
        // 2. 初始化
        for(int i = 0; i < n; i++) dp[i] = 1;
        // 3. 填表
        int ret = 1;
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < i; j++) {
                if(pairs[j][1] < pairs[i][0]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ret = Math.max(dp[i], ret);
        }
        // 4. 返回值
        return ret;

    }


    /**
     * 1218. 最长定差子序列
     */
    public int longestSubsequence(int[] arr, int difference) {
        // // 1. 创建 dp 表
        // // dp[i]表示：以i位置的元素为结尾所有的子序列中，最长的等差子序列的长度
        // int n = arr.length;
        // int[] dp = new int[n];
        // // 2. 初始化
        // for(int i = 0; i < n; i++) dp[i] = 1;
        // // 3. 填表
        // int ret = 1;
        // for(int i = 1; i < n; i++) {
        //     for( int j = 0; j < i; j++) {
        //         if(arr[i] - arr[j] == difference) {
        //             dp[i] = Math.max(dp[j] + 1, dp[i]);
        //         }
        //     }
        //     ret = Math.max(ret, dp[i]);
        // }
        // // 4. 返回值
        // return ret;


        // 1.创建一个哈希表，在哈希表中做 dp
        Map<Integer, Integer> hash = new HashMap<>();

        int ret = 1;
        for(int x : arr) {
            hash.put(x, hash.getOrDefault( x - difference, 0) + 1);
            ret = Math.max(ret, hash.get(x));
        }
        return ret;
    }

    /**
     * 873. 最长的斐波那契子序列的长度
     */
    public int lenLongestFibSubseq(int[] arr) {
        // 优化
        int n = arr.length;
        Map<Integer, Integer> hash = new HashMap<>();
        for(int i = 0; i < n; i++) {
            hash.put(arr[i], i);
        }
        // 1. 创建 dp 表
        // dp[i][j]表示：以i位置以及j位置的元素为结尾的所有的子序列中，最长的斐波那锲子序列长度
        int[][] dp = new int[n][n];
        // 2. 初始化
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                dp[i][j] = 2;
            }
        }
        // 3. 填表
        int ret = 2;
        for(int j = 2; j < n; j++) {
            for(int i = 1; i < j; i++) {
                int a = arr[j] - arr[i];
                if(a < arr[i] && hash.containsKey(a)) {
                    dp[i][j] = dp[hash.get(a)][i] + 1;
                }
                ret = Math.max(ret, dp[i][j]);
            }
        }
        // 4. 返回值
        return ret < 3 ? 0 : ret;
    }

    /**
     * 1027. 最长等差数列
     */
    public int longestArithSeqLength(int[] nums) {
        Map<Integer, Integer> hash = new HashMap<>();
        // 1. 创建 dp 表
        // dp[i][j]表示：以i位置以及j位置的元素为结尾的所有的子序列中，最长的等差序列的长度
        int n = nums.length;
        int[][] dp = new int[n][n];
        // 2. 初始化
        hash.put(nums[0], 0);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                dp[i][j] = 2;
            }
        }
        // 3. 填表
        int ret = 2;
        for(int i = 1; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                int a = 2 * nums[i] - nums[j];
                if(hash.containsKey(a)) {
                    dp[i][j] = dp[hash.get(a)][i] + 1;
                }
                ret = Math.max(ret ,dp[i][j]);
            }
            hash.put(nums[i], i);
        }
        // 4. 返回值
        return ret;
    }

    /**
     * 446. 等差数列划分 II - 子序列
     */
    public int numberOfArithmeticSlices2(int[] nums) {
        // 1. 创建 dp 表
        // dp[i][j]表示：以i位置的元素以及j位置的元素为结尾的所有的子序列中，等差子序列的个数
        int n = nums.length;
        int[][] dp = new int[n][n];
        Map<Long,List<Integer>> hash = new HashMap<>();
        // 2. 初始化
        for(int i = 0; i < n; i++) {
            Long tmp = (long)nums[i];
            if(!hash.containsKey(tmp)) {
                hash.put(tmp, new ArrayList<Integer>());
            }
            hash.get(tmp).add(i);
        }

        // 3. 填表
        int sum = 0;
        for(int j = 2; j < n; j++) {
            for(int i = 1; i < j; i++) {
                Long a = 2L * nums[i] - nums[j];
                if(hash.containsKey(a)) {
                    for(int k : hash.get(a)) {
                        if(k < i) {
                            dp[i][j] += dp[k][i] + 1;
                        }else {
                            break;
                        }
                    }
                }
                sum += dp[i][j];
            }
        }
        // 4. 返回值
        return sum;
    }

    /**
     * 647. 回文子串
     */
    public int countSubstrings(String s) {
        // 1. 创建 dp 表
        // dp[i][j]表示s字符串[i,j]的子串，是否是回文串
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        // 2. 初始化
        // 3. 填表
        int ret = 0;
        for(int i = n-1; i >= 0; i--) {
            for(int j = i; j < n; j++) {
                if(s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = (i + 1 < j) ? dp[i+1][j-1] : true;
                }
                if(dp[i][j]) {
                    ret++;
                }
            }
        }
        // 4. 返回值
        return ret;
    }

    /**
     * 5. 最长回文子串
     */
    public String longestPalindrome(String s) {
        // 1. 创建 dp 表
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        // 2. 初始化
        // 3. 填表
        int begin = 0;
        int len = 1;
        for(int i = n-1; i >= 0; i--) {
            for(int j = i; j < n; j++) {
                if(s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = i + 1 < j ? dp[i+1][j-1] : true;
                }
                if(dp[i][j] && j - i + 1 > len) {
                    len = j - i + 1;
                    begin = i;
                }
            }
        }
        // 4. 返回值
        return s.substring(begin, begin + len);
    }

    /**
     * 1745. 分割回文串 IV
     */
    public boolean checkPartitioning(String s) {
        // 1. 创建 dp 表
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        // 2. 初始化
        // 3. 填表
        // 利用 dp 处理一下所有的子串是否回文
        for(int i = n-1; i >= 0; i--) {
            for(int j = i; j < n; j++) {
                if(s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                }
            }
        }
        // 枚举第二个字符串所有的起始位置和终止位置
        for(int i = 1; i < n - 1; i++) {
            for(int j = i; j < n - 1; j++) {
                if(dp[0][i-1] && dp[i][j] && dp[j+1][n-1]) {
                    return true;
                }
            }
        }
        return false;
        // 4. 返回值

    }


    /**
     * 132. 分割回文串 II
     */
    public int minCut(String s) {
        // 1. 创建 dp 表
        // dp[i]表示：s[0,i]区间上的最长的子串，最少分割次数
        int n = s.length();
        // 预处理
        boolean[][] isPal = new boolean[n][n];
        for(int i = n - 1; i >= 0; i--) {
            for(int j = i; j < n; j++) {
                if(s.charAt(i) == s.charAt(j)) {
                    isPal[i][j] = i + 1 < j ? isPal[i+1][j-1] : true;
                }
            }
        }
        int[] dp = new int[n];

        // 2. 初始化
        for(int i = 0; i < n; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        // 3. 填表
        for(int i = 0; i < n; i++) {
            if(isPal[0][i]) {
                dp[i] = 0;
            }else {
                for(int j = 1; j <= i; j++) {
                    if(isPal[j][i]) {
                        dp[i] = Math.min(dp[i], dp[j - 1] + 1);
                    }
                }
            }
        }
        // 4. 返回值
        return dp[n-1];
    }

    /**
     * 516. 最长回文子序列
     */
    public int longestPalindromeSubseq(String s) {
        // 1. 创建 dp 表
        // dp[i][j]表示：s字符串[i,j]区间内的所有的子序列，最长的回文子序列长度。i<=j
        int n = s.length();
        int[][] dp = new int[n][n];
        // 2. 初始化
        // 3. 填表
        for(int i = n - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for(int j = i + 1; j < n; j++) {
                if(s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i+1][j-1] + 2;
                }else {
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
                }
            }
        }
        // 4. 返回值
        return dp[0][n-1];
    }


    /**
     * 1312. 让字符串成为回文串的最少插入次数
     */
    public int minInsertions(String s) {
        // 1. 创建 dp 表
        // dp[i][j]表示：s里面[i, j]区间内的子串，使他成为回文串的最小插入次数
        int n = s.length();
        int[][] dp = new int[n][n];
        // 2. 初始化
        // 3. 填表
        for(int i = n - 1; i >= 0; i--) {
            for(int j = i + 1; j < n; j++) {
                if(s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i+1][j-1];
                } else {
                    dp[i][j] = Math.min(dp[i+1][j], dp[i][j-1]) + 1;
                }
            }
        }
        // 4. 返回值
        return dp[0][n-1];
    }


    /**
     * 1143. 最长公共子序列
     */
    public int longestCommonSubsequence(String s1, String s2) {
        // 1. 创建 dp 表
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        s1 = " " + s1;
        s2 = " " + s2;
        // 2. 初始化
        // 3. 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(s1.charAt(i) == s2.charAt(j)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        // 4. 返回值
        return dp[m][n];
    }

    /**
     * 1035. 不相交的线
     */
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        // 1. 创建 dp 表
        // dp[i][j]表示：在nums1里面的[0,i]区间以及nums2里面的[0,j]区间里面的所有的子序列中，最长公共子序列的长度
        int m = nums1.length;
        int n = nums2.length;
        int[][] dp = new int[m+1][n+1];
        // 2. 初始化
        // 3. 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(nums1[i-1] == nums2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        // 4. 返回值
        return dp[m][n];
    }

    /**
     * 115. 不同的子序列
     */
    public int numDistinct(String s, String t) {
        // 1. 创建 dp 表
        // dp[i][j]表示：s字符串[0,j]区间内所有的子序列中，有多少个t字符串[0,i]区间的子串
        int m = t.length();
        int n = s.length();
        int[][] dp = new int[m+1][n+1];
        s = " " + s;
        t = " " + t;
        // 2. 初始化
        for(int j = 0; j <= n; j++) {
            dp[0][j] = 1;
        }
        // 3. 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = dp[i][j-1] + (t.charAt(i) == s.charAt(j) ? dp[i-1][j-1] : 0);
            }
        }
        // 4. 返回值
        return dp[m][n];
    }

    /**
     * 44. 通配符匹配
     */
    public boolean isMatch(String s, String p) {
        // 1. 创建 dp 表
        // dp[i][j]表示：p[0,j]区间内的子串能否匹配s[0,i]区间内的子串
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m+1][n+1];
        s = " " + s;
        p = " " + p;
        // 2. 初始化
        dp[0][0] = true;
        for(int j = 1; j <= n; j++) {
            if(p.charAt(j) == '*') {
                dp[0][j] = true;
            }else {
                break;
            }
        }
        // 3. 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(p.charAt(j) == '*') {
                    dp[i][j] = dp[i-1][j] || dp[i][j-1];
                } else {
                    dp[i][j] = (p.charAt(j) == '?' || s.charAt(i) == p.charAt(j)) && dp[i-1][j-1];
                }
            }
        }
        // 4. 返回值
        return dp[m][n];
    }

    /**
     * 10. 正则表达式匹配
     */
    public boolean isMatch2(String s, String p) {
        // 1. 创建 dp 表
        // dp[i][j]表示：p[0,j]区间内的子串能否匹配s[0,i]区间内的子串
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m+1][n+1];
        s = " " + s;
        p = " " + p;
        // 2. 初始化
        dp[0][0] = true;
        for(int j = 2; j <= n; j += 2) {
            if(p.charAt(j) == '*') {
                dp[0][j] = true;
            }else {
                break;
            }
        }
        // 3. 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(p.charAt(j) == '*') {
                    dp[i][j] = dp[i][j-2] || (p.charAt(j-1) == '.' || p.charAt(j-1) == s.charAt(i)) && dp[i-1][j];
                }else {
                    dp[i][j] = (s.charAt(i) == p.charAt(j)
                            || p.charAt(j) == '.') && dp[i-1][j-1];

                }
            }
        }
        // 4. 返回值
        return dp[m][n];
    }


    /**
     * 97. 交错字符串
     */
    public boolean isInterleave(String ss1, String ss2, String ss3) {
        // 1. 创建 dp 表
        // dp[i][j]表示：s1中[1,i]区间内的字符串以及s2中[1,j]区间内的字符串，能否拼接凑成s3[1,i+j]区间内的字符串
        int m = ss1.length();
        int n = ss2.length();
        if(m + n != ss3.length()) return false;
        boolean[][] dp = new boolean[m+1][n+1];
        ss1 = " " + ss1;
        ss2 = " " + ss2;
        ss3 = " " + ss3;
        char[] s1 = ss1.toCharArray();
        char[] s2 = ss2.toCharArray();
        char[] s3 = ss3.toCharArray();
        // 2. 初始化
        dp[0][0] = true;
        for(int i = 1; i <= m; i++) {
            if(s1[i] == s3[i]) {
                dp[i][0] = true;;
            }else {
                break;
            }
        }
        for(int j = 1; j <= n; j++) {
            if(s2[j] == s3[j]) {
                dp[0][j] = true;
            }else {
                break;
            }
        }
        // 3. 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = (s1[i] == s3[i+j] && dp[i-1][j]) || (s2[j] == s3[i+j] && dp[i][j-1]);
            }
        }
        // 4. 返回值
        return dp[m][n];

    }


    /**
     * 712. 两个字符串的最小ASCII删除和
     */
    public int minimumDeleteSum(String s1, String s2) {
        // 1. 创建 dp 表
        // dp[i][j]表示：s1的[0,i]区间以及s2的[0,j]区间内的所有的子序列里，公共子序列的ASCII最大和
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m+1][n+1];
        // 2. 初始化
        // 3. 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                if(s1.charAt(i-1) == s2.charAt(j-1)) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1] + s1.charAt(i-1));
                }
            }
        }
        // 4. 返回值
        int sum = 0;
        for(char ch : s1.toCharArray()) sum += ch;
        for(char ch : s2.toCharArray()) sum += ch;
        return sum - dp[m][n] - dp[m][n];
    }

    /**
     * 718. 最长重复子数组
     */
    public int findLength(int[] nums1, int[] nums2) {
        // 1. 创建 dp 表
        // dp[i][j]表示：nums1中以i位置为结尾的所有的子数组以及num2中以j位置元素为结尾的所有子数组中，最长重复子数组的长度
        int m = nums1.length;
        int n = nums2.length;
        int[][] dp = new int[m+1][n+1];
        // 2. 初始化
        // 3. 填表
        int ret = 0;
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(nums1[i-1] == nums2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    ret = Math.max(ret, dp[i][j]);
                }
            }
        }
        // 4. 返回值
        return ret;
    }


    /**
     *  416. 分割等和子集
     */
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if(sum % 2 != 0) return false;
        // 1. 创建 dp 表
        // dp[i][j]表示：从前i个数中选，所有的选法中，能否凑成j这个数
        int n = nums.length;
        boolean[][] dp = new boolean[n+1][sum/2+1];
        // 2. 初始化
        for(int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }
        // 3. 填表
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= sum/2; j++) {
                dp[i][j] = dp[i-1][j];
                if(j >= nums[i-1]) {
                    dp[i][j] = dp[i][j] || dp[i-1][j-nums[i-1]];
                }
            }
        }
        // 4. 返回值
        return dp[n][sum/2];
    }

    //优化 - 滚动数组
    public boolean canPartition2(int[] nums) {
        int sum = 0;
        for(int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if(sum % 2 != 0) return false;
        // 1. 创建 dp 表
        // dp[i][j]表示：从前i个数中选，所有的选法中，能否凑成j这个数
        int n = nums.length;
        boolean[] dp = new boolean[sum/2+1];
        // 2. 初始化
        dp[0] = true;
        // 3. 填表
        for(int i = 1; i <= n; i++) {
            for(int j = sum/2; j >= nums[i-1]; j--) {
                dp[j] = dp[j] || dp[j-nums[i-1]];

            }
        }
        // 4. 返回值
        return dp[sum/2];
    }


    /**
     * 494. 目标和
     */
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        int sum = 0;
        for(int x : nums) sum += x;
        int a = (target  + sum) / 2;
        if(a < 0 || (sum + target) % 2 != 0) return 0;
        // 1. 创建 dp 表
        // dp[i][j]表示：从前i个数中选，总和正好等于j,一共有多少种选法
        int[][] dp = new int[n+1][a+1];
        // 2. 初始化
        dp[0][0] = 1;
        // 3. 填表
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= a; j++) {
                dp[i][j] = dp[i-1][j];
                if(j >= nums[i-1]) {
                    dp[i][j] += dp[i-1][j-nums[i-1]];
                }
            }
        }
        // 4. 返回值
        return dp[n][a];
    }
    // 优化
    public int findTargetSumWays2(int[] nums, int target) {
        int n = nums.length;
        int sum = 0;
        for(int x : nums) sum += x;
        int a = (target  + sum) / 2;
        if(a < 0 || (sum + target) % 2 != 0) return 0;
        // 1. 创建 dp 表
        // dp[i][j]表示：从前i个数中选，总和正好等于j,一共有多少种选法
        int[] dp = new int[a+1];
        // 2. 初始化
        dp[0] = 1;
        // 3. 填表
        for(int i = 1; i <= n; i++) {
            for(int j = a; j >= nums[i-1]; j--) {
                dp[j] += dp[j-nums[i-1]];
            }
        }
        // 4. 返回值
        return dp[a];
    }


    /**
     * 1049. 最后一块石头的重量 II
     */
    public int lastStoneWeightII(int[] stones) {
        int n = stones.length;
        int sum = 0;
        for(int x : stones) sum += x;
        int m = sum / 2;
        // 1. 创建 dp 表
        // dp[i][j]表示：从前i个数中选，总和不超过j，此时的最大和
        int[][] dp = new int[n+1][m+1];
        // 2. 初始化
        // 3. 填表
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= m; j++) {
                dp[i][j] = dp[i-1][j];
                if(j >= stones[i - 1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-stones[i-1]] + stones[i-1]);
                }
            }
        }
        // 4. 返回值
        return sum - 2 * dp[n][m];
    }
    //优化
    public int lastStoneWeightII2(int[] stones) {
        int n = stones.length;
        int sum = 0;
        for(int x : stones) sum += x;
        int m = sum / 2;
        // 1. 创建 dp 表
        // dp[i][j]表示：从前i个数中选，总和不超过j，此时的最大和
        int[] dp = new int[m+1];
        // 2. 初始化
        // 3. 填表
        for(int i = 1; i <= n; i++) {
            for(int j = m; j >= stones[i - 1]; j--) {
                dp[j] = Math.max(dp[j], dp[j-stones[i-1]] + stones[i-1]);
            }
        }
        // 4. 返回值
        return sum - 2 * dp[m];
    }

    /**
     * 322. 零钱兑换
     */
    static int INF = 0x3f3f3f3f;
    public int coinChange(int[] coins, int amount) {
        // 1. 创建 dp 表
        // dp[i][j]表示：从前i个硬币中选，总和正好等于j所有的选法中，最少的硬币个数
        int n = coins.length;
        int[][] dp = new int[n+1][amount+1];
        // 2. 初始化
        for(int j = 1; j <= amount; j++) {
            dp[0][j] = INF;
        }
        // 3. 填表
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= amount; j++) {
                dp[i][j] =dp[i-1][j];
                if(j >= coins[i-1]) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][j-coins[i-1]] + 1);
                }
            }
        }
        // 4. 返回值
        return (dp[n][amount] >= INF ? -1 : dp[n][amount]);
    }

    // 优化
    public int coinChange2(int[] coins, int amount) {
        // 1. 创建 dp 表
        // dp[i][j]表示：从前i个硬币中选，总和正好等于j所有的选法中，最少的硬币个数
        int n = coins.length;
        int[] dp = new int[amount + 1];
        // 2. 初始化
        for (int j = 1; j <= amount; j++) {
            dp[j] = INF;
        }
        // 3. 填表
        for (int i = 1; i <= n; i++) {
            for (int j = coins[i - 1]; j <= amount; j++) {
                dp[j] = Math.min(dp[j], dp[j - coins[i - 1]] + 1);
            }
        }
        // 4. 返回值
        return (dp[amount] >= INF ? -1 : dp[amount]);
    }

    /**
     * 518. 零钱兑换 II
     * @param amount
     * @param coins
     * @return
     */
    public int change(int amount, int[] coins) {
        // 1. 创建 dp 表
        // dp[i][j]表示：从前i个硬币中挑选，总和正好等于j，一共有多少种选法
        int n = coins.length;
        int[][] dp = new int[n+1][amount+1];
        // 2. 初始化
        dp[0][0] = 1;
        // 3. 填表
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= amount; j++) {
                dp[i][j] = dp[i-1][j];
                if(j >= coins[i-1]) {
                    dp[i][j] += dp[i][j-coins[i-1]];
                }
            }
        }
        // 4. 返回值
        return dp[n][amount];
    }
    // 优化
    public int change2(int amount, int[] coins) {
        // 1. 创建 dp 表
        // dp[i][j]表示：从前i个硬币中挑选，总和正好等于j，一共有多少种选法
        int[] dp = new int[amount+1];
        // 2. 初始化
        dp[0] = 1;
        // 3. 填表
        for(int x : coins) {
            for(int j = x; j <= amount; j++) {
                dp[j] += dp[j - x];
            }
        }
        // 4. 返回值
        return dp[amount];
    }

    /**
     * 279. 完全平方数
     */
    public int numSquares(int n) {
        // 1. 创建 dp 表
        // dp[i][j]表示：从前i个完全平方数中挑选，总和正好等于j，所有的选法中，最小的数量
        int INF = 0x3f3f3f3f;
        int m = (int)Math.sqrt(n);
        int[][] dp = new int[m+1][n+1];
        // 2. 初始化
        for(int j = 1; j <= n; j++) {
            dp[0][j] = INF;
        }
        // 3. 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 0; j <= n; j++) {
                dp[i][j] = dp[i-1][j];
                if(j >= i * i) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][j - i * i] + 1);
                }
            }
        }
        // 4. 返回值
        return dp[m][n];
    }
    // 优化
    public int numSquares2(int n) {
        // 1. 创建 dp 表
        // dp[i][j]表示：从前i个完全平方数中挑选，总和正好等于j，所有的选法中，最小的数量
        int INF = 0x3f3f3f3f;
        int m = (int)Math.sqrt(n);
        int[] dp = new int[n+1];
        // 2. 初始化
        for(int j = 1; j <= n; j++) {
            dp[j] = INF;
        }
        // 3. 填表
        for(int i = 1; i <= m; i++) {
            for(int j = i * i; j <= n; j++) {
                dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
            }
        }
        // 4. 返回值
        return dp[n];
    }


    /**
     * 474. 一和零
     */
    public int findMaxForm(String[] strs, int m, int n) {
        // 1. 创建 dp 表
        // dp[i][j][k]表示：从前i个字符串中挑选，字符0的个数不超过j，字符1的个数不超过k，所有的选法中，最大的长度
        int len = strs.length;
        int[][][] dp = new int[len+1][m+1][n+1];
        // 2. 初始化
        // 3. 填表
        for(int i = 1; i <= len; i++) {
            // 统计一下字符串中 0 1 的个数
            int a = 0;
            int b = 0;
            for(char ch : strs[i - 1].toCharArray()) {
                if(ch == '0') a++;
                else b++;
            }
            for(int j = 0; j <= m; j++) {
                for(int k = 0; k <= n; k++) {
                    dp[i][j][k] = dp[i-1][j][k];
                    if(j >= a && k >= b) {
                        dp[i][j][k] = Math.max(dp[i][j][k], dp[i-1][j-a][k-b] + 1);
                    }
                }
            }
        }
        // 4. 返回值
        return dp[len][m][n];
    }
    // 优化
    public int findMaxForm2(String[] strs, int m, int n) {
        // 1. 创建 dp 表
        // dp[i][j][k]表示：从前i个字符串中挑选，字符0的个数不超过j，字符1的个数不超过k，所有的选法中，最大的长度
        int len = strs.length;
        int[][] dp = new int[m+1][n+1];
        // 2. 初始化
        // 3. 填表
        for(int i = 1; i <= len; i++) {
            // 统计一下字符串中 0 1 的个数
            int a = 0;
            int b = 0;
            for(char ch : strs[i - 1].toCharArray()) {
                if(ch == '0') a++;
                else b++;
            }
            for(int j = m; j >= a; j--) {
                for(int k = n; k >= b; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j-a][k-b] + 1);

                }
            }
        }
        // 4. 返回值
        return dp[m][n];
    }

    /**
     * 879. 盈利计划
     */
    public int profitableSchemes(int n, int m, int[] g, int[] p) {
        // 1. 创建 dp 表
        // dp[i][j][k]表示：从前i个计划中挑选，总人数超过j，总利润至少为k，一共有多少种选法
        int len = g.length;
        int[][][] dp = new int[len + 1][n + 1][m + 1];
        int MOD = (int)1e9 + 7;
        // 2. 初始化
        for(int j = 0; j <= n; j++) {
            dp[0][j][0] = 1;
        }
        // 3. 填表
        for(int i = 1; i <= len; i++) {
            for(int j = 0; j <= n; j++) {
                for(int k = 0; k <= m; k++) {
                    dp[i][j][k] = dp[i - 1][j][k];
                    if(j >= g[i-1]) {
                        dp[i][j][k] += dp[i-1][j-g[i-1]][Math.max(0, k - p[i-1])];
                        dp[i][j][k] %= MOD;
                    }
                }
            }
        }
        // 4. 返回值
        return dp[len][n][m];

    }
    // 优化
    public int profitableSchemes2(int n, int m, int[] g, int[] p) {
        // 1. 创建 dp 表
        // dp[i][j][k]表示：从前i个计划中挑选，总人数超过j，总利润至少为k，一共有多少种选法
        int len = g.length;
        int[][] dp = new int[n + 1][m + 1];
        int MOD = (int)1e9 + 7;
        // 2. 初始化
        for(int j = 0; j <= n; j++) {
            dp[j][0] = 1;
        }
        // 3. 填表
        for(int i = 1; i <= len; i++) {
            for(int j = n; j >= g[i - 1]; j--) {
                for(int k = m; k >= 0; k--) {
                    dp[j][k] += dp[j - g[i - 1]][Math.max(0, k - p[i - 1])];
                    dp[j][k] %= MOD;
                }
            }
        }
        // 4. 返回值
        return dp[n][m];

    }

    /**
     * 377. 组合总和 Ⅳ
     */
    public int combinationSum4(int[] nums, int target) {
        // 1. 创建 dp 表
        // dp[i]表示凑成总和为i，一共有多少种排列数
        int[] dp = new int[target + 1];
        // 2. 初始化
        dp[0] = 1;
        // 3. 填表
        for(int i = 1; i <= target; i++) {
            for(int x : nums) {
                if(i >= x) {
                    dp[i] += dp[i - x];
                }
            }
        }
        // 4. 返回值
        return dp[target];

    }

    /**
     * 96. 不同的二叉搜索树
     */
    public int numTrees(int n) {
        // 1. 创建 dp 表
        // dp[i]表示：节点个数为i的时候，一共有多少种二叉搜索树
        int[] dp = new int[n + 1];
        // 2. 初始化
        dp[0] = 1;
        // 3. 填表
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        // 4. 返回值
        return dp[n];

    }

        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值






}






































